package com.zhupf.dynamic;

import java.util.Arrays;

/**
 * @author zhupf
 * @date 2024年03月28日 10:36
 * @Description 322. 零钱兑换
 */
public class CoinChange {

    public static void main(String[] args) {
        int[] coins = {1,2,5};
        System.out.println(coinChange(coins, 11));
    }


    public static int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        Arrays.fill(dp,amount+1);
        dp[0] = 0;
        for(int i = 1 ;i<= amount;i++){
            for (int coin : coins) {
                if(coin>i){
                    continue;
                }
                dp[i] = Math.min(dp[i],dp[i-coin]+1);
            }
        }
        return dp[amount] == amount+1?-1:dp[amount];
    }




    public static int coinChange1(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        return process(coins,amount,dp);
    }

    public static int process(int[] coins, int n,int[] dp) {
        if (n == 0) {
            return 0;
        }
        if (n < 0) {
            return -1;
        }
        if(dp[n] != 0){
            return dp[n];
        }
        int res = Integer.MAX_VALUE;
        for (int coin : coins) {
            int ans = process(coins, n - coin,dp);
            if (ans == -1) {
                continue;
            }
            res = Math.min(res, ans);
        }
        dp[n] = res ==  Integer.MAX_VALUE ? -1 : res + 1;
        return dp[n];
    }

}
